home *** CD-ROM | disk | FTP | other *** search
- Path: mail2news.demon.co.uk!genesis.demon.co.uk
- From: Lawrence Kirby <fred@genesis.demon.co.uk>
- Newsgroups: comp.std.c
- Subject: Re: Restrictions on qsort compare function?
- Date: Thu, 04 Apr 96 18:57:54 GMT
- Organization: none
- Message-ID: <828644274snz@genesis.demon.co.uk>
- References: <4iokop$h4p@lyra.csx.cam.ac.uk> <4iqjar$2m9@usenet.pa.dec.com> <4jgltp$f9l@lyra.csx.cam.ac.uk>
- Reply-To: fred@genesis.demon.co.uk
- X-NNTP-Posting-Host: genesis.demon.co.uk
- X-Newsreader: Demon Internet Simple News v1.27
- X-Mail2News-Path: genesis.demon.co.uk
-
- In article <4jgltp$f9l@lyra.csx.cam.ac.uk>
- jkb@mrc-lmb.cam.ac.uk "James Bonfield" writes:
-
- >I now agree that non antisymmetric or nontransitive sort comparison functions
- >are indeed invalid. I can see how this can be construed from the ansi
- >standard, but can also see how it's possible to construe otherwise.
-
- I don't. 7.10.5.2:
-
- "The contents of the array are sorted into ascending
- order according to a comparison function pointed to by compar".
-
- If the comparison function produces inconsistent results then it is at odds
- with that sentence. At best that sentence has no well-defined meaning and
- the 'sort' operation as a whole has undefined behaviour.
-
- >it doesn't really state such things explicitly. Anyway, that aside I thought I
- >should reply to the last note about this.
- >
- >In article <4iqjar$2m9@usenet.pa.dec.com> diamond@tbj.dec.com (Norman Diamond)
- > writes:
- >
- >>>such functions appear to make [one implementation's] qsort() function
- >>>underflow the passed array.
- >>
- >>This should not happen.
- >
- >Well, that depends on whether or not you class qsorts behaviour as undefined
- >for such functions.
-
- To put it another way, if there is a defined behaviour with such a function,
- what is it?
-
- >>>#define NUM_ELE 10
- >>>int main() {
- >>> int i;
- >>> int crashme; /* removing this line fixes things! */
- >>
- >>This makes me suspicious that your test program is not exactly what you
- >>posted, and your test program has a bug in some other part of its code
- >>that already yielded undefined behavior.
- >
- >Actually it's true - it does cause it to go wrong. I've got an example now
- >that used explicitly defined numbers to cause a crash. With the crashme line
- >in the program dies. Without it the program modifies memory not within the
- >boundaries of qsort. My program is:
- >
- >#include <stdio.h>
- >#include <stdlib.h>
- >
- >static int sort_func(const void *pa, const void *pb)
- >{
- > const int *a = (int *)pa;
- > const int *b = (int *)pb;
-
- It would be more consistent (as well as killing a warning from my compiler)
- if you cast to (const int *), better still don't cast at all.
-
- >
- > return *a > *b;
- >}
-
- This clearly violates a 'shall' in the standard and results in undefined
- behaviour. With the specific data in this case return *a - *b; would be OK.
-
- "The function shall return an integer less than, equal to, or greater than
- zero if the first argument is considered to be respectively less than, equal
- to, or greater than the second."
-
- >#define NUM_ELE 10
- >int main() {
- > int i;
- > int crashme; /* removing this line fixes things! */
- > int sortme[NUM_ELE] = {148, 104, 126, 74, 108, 131, 129, 131, 125, 77};
- >
- > for (i=0; i<NUM_ELE; i++) printf("%d ", sortme[i]);
- > putchar('\n');
- >
- > qsort((void *)(sortme+1), NUM_ELE-2, sizeof(int), sort_func);
- >
- > for (i=0; i<NUM_ELE; i++) printf("%d ", sortme[i]);
- > putchar('\n');
- >
- > return 0;
- >}
- >
- >>b < c and c < a). As for whether qsort() is required to contend with
- >>such nonsense, it "probably" isn't.
- >
- >Agreed. Hence the above discoveries are most likely entirely within the realm
- >of acceptability.
- >
- >Perhaps the most interesting point to come out of this is the inefficiency of
- >some qsort algorithms. Sorting 100,000 elements (with a "consistent" sort
- >comparison function) gave the following approximations (ran several times with
- >random input - of course these results may just reflect the random number
- >generator woes!):
- >
- >OSF/1 V3.0 ~72K
- >Linux (gnu lib) ~153K
- >Irix 5.3 ~170K
- >Solaris 5.3 ~305K
-
- What do these numbers represent?
-
- --
- -----------------------------------------
- Lawrence Kirby | fred@genesis.demon.co.uk
- Wilts, England | 70734.126@compuserve.com
- -----------------------------------------
-